package Leetcode第一期;

/**
 * @author : K k
 * @date : 11:49 2020/10/5
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL

 */
public class 反转链表II_92 {

    //思路：头插法
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode node =new ListNode(0);
        node.next=head;
        ListNode g=head,p=head.next;

        int step=0;
        while (step<m-1){
            g=g.next;
            p=p.next; //此时的p是m位置的结点
            step++;
        }

        for (int i=0;i<n-m;i++){
            ListNode removed=p.next;
            p.next=removed.next;
            removed.next=g.next;
            g.next=removed;
        }
        return node.next;
    }
}
